package com.ruoyi.system.spi;

public class Client0418 {

    // 选满
    public static int knapsack(int[] weight, int[] value, int maxweight) {

        // 动态规划  重量和 物品
        int n = value.length;
        int[][] dp = new int[n][maxweight + 1];
        try {
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < maxweight + 1; j++) {
                    if (i == 0) { // 只选第一个的时候， 只有是整数倍才能有值，其他的都是最小值，，不能选的。
                        if (j >= weight[0] && j % weight[i] == 0) {
                            int k = j / weight[i];
                            // 第一个物品可以多次选择，只要满足条件
                            dp[i][j] = k * value[i];
                        } else {
                            dp[i][j] = Integer.MIN_VALUE;
                        }
                        continue;
                    }
                    if (j >= weight[i]) {
                        int k = j / weight[i];
                        for (int key = 0; key <= k; key++) {
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - key * weight[i]] + key * value[i]);
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }

                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return dp[n - 1][maxweight];
    }

    // 买卖股票最大时机 动态规划解法
    public static int maxProfit(int[] prince) {
        // 定义二维数组表示最大利润，获取最大值 0代表持有 、1代表卖出
        int[][] dp = new int[prince.length][2];
        // 初始化值
        dp[0][0] = -prince[0];
        dp[0][1] = 0;
        int length = prince.length;
        //  这是操作一次的操作。
        for (int i = 1; i < length; i++) {
            // 第 i 天持有
            // 操作多次呢

            dp[i][0] = Math.max(dp[i - 1][0], -prince[i]);
            // 第i 天不持有  为啥不是前一天持有，并且卖掉了呢？
            dp[i][1] = Math.max(dp[i-1][0] + prince[i], dp[i - 1][1]);
        }

        // 返回 i 天不持有
        return dp[prince.length - 1][1];
    }


    // 最多time 次交易    1 4 5
    public static int maxProfit(int[] prince, int time) {
        //  既有 天数的变化， 又有交易次数的变化
        // 表示总的利润随  交易天数和选择次数

        // 交易天数  和  这次操作是否持有
        int[][] dp = new int[prince.length][2 * time + 1];  //  某一天在某次操作下是否持有的最大利润。
        // 交易天数固定时，的动态规划
        for (int j = 0; j < prince.length; j++) {
            for (int i = 1; i < 2 * time + 1; i++) {
                // 持有
                dp[j][i] = Math.max(dp[j - 1][i], dp[j - 1][i - 1] - prince[i]);
                // 不持有  不操作的数据时体现在哪里呢？
                dp[j][i + 1] = Math.max(dp[j - 1][i + 1], dp[j - 1][i] + prince[i]);
            }
        }


        return 0;
    }

    //  最大利润解法二
    public static int maxProfit1(int[] prince) {

        int length = prince.length;
        int small = prince[0];
        int maxprofit = 0;
        for (int i = 0; i < length; i++) {
            if (prince[i] > small) {
                maxprofit = Math.max(prince[i] - small, maxprofit);
            } else {
                small = prince[i];
            }
        }

        return maxprofit;
    }

    public static void main(String[] args) {

        int[] price = {1, 2, 3, 4, 8};
        int[] seat = {0, 1, 0, 0, 0, 0};
        System.out.println(maxDistToClosest(seat));
    }

    //  最近人的最大距离 相当于是求连续0最多的时候 可以用双指针
    public static int maxDistToClosest(int[] seats) {
        int left = -1;
        int right = 0;
        int maxlength = 0;
        int length = seats.length;
        int begin = 0;
        for (int i = 0; i < length; i++) {
            if (seats[i] == 0) {
                right = i;
            } else {
                // 有人，移动左边指针 并计算当前最大值
                // 前面全是 0
                begin = begin == 0 ? i : begin;
                maxlength = Math.max(maxlength, right - left);
                left = i;
            }
        }
        int maxDist = (maxlength + 1) / 2;
        // 最后存在连续0
        if (right == length - 1) {
            maxDist = Math.max(maxDist, right - left);
        }
        // 最前面存在连续 0
        if (begin > 0) {
            maxDist = Math.max(maxDist, begin);
        }
        return maxDist;

    }
}
